package a12_SeqList.DoubleLinkedList;

import a12_SeqList.ArrayList.SeqList;

/**
 * @Author quan
 * @Description 双向链表
 * @Date 2023/3/19 16:04
 */
public class DoubleLinkedList<E> implements SeqList<E> {
    private int size;//节点个数
    private DoubleNode head;//头节点
    private DoubleNode tail;//尾结点
    public class DoubleNode{
        DoubleNode prev;//前驱
        DoubleNode next;//后继
        E val;//值

        public DoubleNode(E val) {
            this.val = val;
        }

        public DoubleNode(DoubleNode prev, DoubleNode next, E val) {
            this.prev = prev;
            this.next = next;
            this.val = val;
        }
    }
    /**
     * 增：尾插
     * 思想：判断节点是否存在：
     * 如果头结点为null，则直接返回null；
     * 如果有节点存在：产生新节点——>新节点的prev指向尾结点的tail，将尾结点的next指向新节点——>更新tail的位置——>size++
     */
    @Override
    public void add(E element) {
        //产生新节点
        DoubleNode node = new DoubleNode(element);
        //边界条件:如果头结点为空，没有节点，则该插入的节点就是新的头结点
        if(head == null){
            head = node;
        }else{//如果存在头结点，则正常尾插
          //更改指向
            node.prev = tail;
            tail.next = node;
        }
        //更新尾结点和节点数
        tail = node;
        size++;
    }
    /** 头插:特殊情况：当不存在节点时，此时的头插就是将新产生的节点作为尾结点
     */
    public void addFirst(E element){
        DoubleNode node = new DoubleNode(element);
        //当原链表中不存在节点时:-------这里理解一下if的边界条件
        if(tail == null){
            tail = node;
        }else{//原链表中有节点存在时
            node.next = head;
            head.prev = node;
        }
        head = node;
        size++;
    }
    /**
     * 增：根据索引插入元素
     */
    @Override
    public void add(int index, E element) {
        //索引的合法性判断
        if(!indexCheck(index)){
            throw new IllegalArgumentException("add index illegal");
        }
        //边界条件的判断:如果是在索引为0的位置进行元素的插入，那就直接调用头插方法
        if(index == 0){
            addFirst(element);
            return;
        }//如果是在索引为size的位置插入元素，则直接调用尾插方法:size表示当前列表中所有节点的个数
        if(index == size){
            add(element);
            return;
        }
        //-------这里不懂：调试代码发现这里通过node返回的result就是要插入索引位置的前一个结点--------
        DoubleNode prev = NodeLocation(index-1);
        DoubleNode next = prev.next;
        DoubleNode node = new DoubleNode(element);
        //更改节点指向：左半部分(这里两部分的顺序不影响结果)
        node.prev = prev;
        prev.next = node;
        //右半部分
        next.prev = node;
        node.next = next;
        //更新节点数
        size++;
    }

    /**
     * 这个还是理解起来有点困难：不知道为什么要写这个函数
     * 内部使用的工具方法：根据索引判判断与中间位置的前后关系,决定到底是从前向后寻找节点还是从后向前寻找节点
     */
    private DoubleNode NodeLocation(int index){
        DoubleNode result = null;
        if(index < (size>>1)){
            result = head;
            for (int i = 0; i < index; i++) {
                result = result.next;
            }
        }else{
            result = tail;
            for (int i = size-1; i > index ; i--) {
                result = result.prev;
            }
        }
        return result;
    }
    /**
     * 删：通过索引删除元素
     * 思想：每个被删除的节点都有一个前节点和后节点，此时我们先找到被删除的节点，再找到被删除节点的前后节点。
     * 然后更改节点的指向。
     * 要注意的是：前后节点有两种情况，也就是存在和不存在的情况，排列组合也就是4种情况：
     * (1)前节点不存在，后节点存在：也就是头删——>要更新头结点的位置
     * (2)前节点存在，后节点不存在，也就是尾删——>要更新尾结点的位置
     * (3)前后节点都存在，在中间位置的删除
     * (4)前后节点都不存在，说明是只存在一个节点或者是没有节点存在
     */
    @Override
    public E removeByIndex(int index) {
        //判断索引的合法性
        if(!indexCheck(index)){
            throw new IllegalArgumentException("remove index illegal");
        }
        //通过NodeLocation函数，传入索引值找到被删除的节点node
        DoubleNode node = NodeLocation(index);
        //删除节点node
        removeNodeFun(node);
        return node.val;//返回被删除节点的值
    }
    //方法：findRelativeNode的作用是先找到删除节点的前后节点，然后排列组合4种情况删除节点
    private void removeNodeFun(DoubleNode node) {
        DoubleNode prev = node.prev;//前节点
        DoubleNode next = node.next;//后节点
        //先处理被删除节点的左半部分
        if(node.prev == null){//前节点不存在
            head = next;//更新头结点
        }else{//前节点存在
            node.prev = null;
            prev.next = next;
        }
        //再处理被删除节点的右半部分
        if(node.next == null){//后节点不存在
            tail = prev;//更新尾结点
        }else{//后节点存在
            node.next = null;
            next.prev = prev;
        }
        //更新节点数
        size--;
    }
    /**
     * 删：删除链表中出现的第一个元素
     * 从头结点开始不断遍历链表，找到被删除的节点删除并结束方法
     */
    @Override
    public void removeByValue(E element) {
        //让node接收head的值
        DoubleNode node = head;
        //遍历整个链表，走到与被删除的节点值相等的位置
        for (int i = 0; i < size; i++) {
            if(node.val.equals(element)){
                //使用removeNodeFun函数删除node节点
                removeNodeFun(node);
                return;
            }
            node = node.next;//不断移动node的位置
        }
    }
    /**
     * 删除出现的所有为element的元素：刚开始自己写的时候直接去掉上面的return，觉得就可以了，但是报错空指针异常
     * 后来发现是因为遍历的长度为size，也就是链表的长度，但是每一次找到要删除的元素值后，链表中的节点个数就会发生变化
     * 因此这里不能用size，应该用一个临时变量 来接收size的值作为固定长度
     */
    @Override
    public void removeAllValue(E element) {
        //让node接收head的值
        DoubleNode node = head;
        //取链表的长度
        int length = size;
        //遍历整个链表，走到与被删除的节点值相等的位置
        for (int i = 0; i < length; i++) {
            //这里要注意：之前自己写的时候，DoubleNode next = node.next;和  node = next;写为一句凡在for循环里的最后，但是会报空指针异常
            //个人理解：因为出现多个要被删除的值，这个时候要先获取每个节点的下一个节点进行接收，否则如果这个节点被删除了，下一个节点就找不到了，指向的是null
            DoubleNode next = node.next;
            if(node.val.equals(element)){
                //使用removeNodeFun函数删除node节点
                removeNodeFun(node);
            }
            node = next;//不断移动node的位置
        }
    }

    @Override
    public E set(int index, E element) {
        //判断索引的合法性
        if(!indexCheck(index)){
            throw new IllegalArgumentException("set index illegal");
        }
        //从头结点开始从前向后走到index对应的元素：但是注意不能直接使用head，head不断后移会导致链表发生变化最后丢失。所以这里用一个新的节点x存储head的位置
        DoubleNode x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        //此时x就走到了待修改位置，也就是索引位置
        E oldVal = x.val;//获取原链表的旧值
        x.val = element;//设置新值
        return oldVal;//返回旧值
    }
    /**
     * 查：获取Index的元素
     */
    @Override
    public E get(int index) {
        //判断索引的合法性
        if(!indexCheck(index)){
            throw new IllegalArgumentException("get index illegal");
        }
        //直接返回索引位置下的元素值
        return NodeLocation(index).val;
    }

    private boolean indexCheck(int index) {
        if(index<0 || index>size){
            return false;
        }else{
            return true;
        }
    }
    /**
     * contains：判断该元素是否被包含在链表中，返回boolean类型的值
     */
    @Override
    public boolean contains(E element) {
        //遍历链表，判断链表中的每个节点的元素值是否与传入的element值相等
        DoubleNode node = head;//用node代替head
        for (int i = 0; i < size; i++) {
            if(node.val.equals(element)){
                return true;
            }
            node = node.next;//不断移动到下一个节点
        }
        return false;
    }
    /**
     * indexOf:返回查找元素element的索引值
     * 如果是多个重复元素，返回第一个查找到元素值的索引
     */
    @Override
    public int indexOf(E element) {
        //遍历链表，判断链表中的每个节点的元素值是否与传入的element值相等
        DoubleNode node = head;//用node代替head
        for (int i = 0; i < size; i++) {
            if(node.val.equals(element)){
                return i;
            }
            node = node.next;//不断移动到下一个节点
        }
        throw new IllegalArgumentException("没有找到该元素");
    }
    /**
     * 重写toString方法
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (DoubleNode x = head; x != null ; x=x.next) {
            sb.append(x.val).append("——>");
            if(x == tail){
                sb.append("Null\n");
            }
        }
        return sb.toString();
    }
}
